|
KMID : 1144120110010040239
|
|
Biomedical Engineering Letters
2011 Volume.1 No. 4 p.239 ~ p.246
|
|
|
A novel algorithm for restricting the complexity of virus typing via PCR-RFLP gel electrophoresis
|
|
Maramis Christos F.
Delopoulos Anastasios N.
|
|
|
Abstract
|
|
|
Purpose: PCR-RFLP gel electrophoresis is a popular method for virus typing (i.e., for identifying the types of a virus that have infected a biological sample), which has been automated recently owing to a computerized typing methodology. However, even with the help of this methodology, the PCRRFLP method suffers from low throughput, when compared to other typing methods. In this paper, we tackle this issue by introducing a novel algorithm for conducting the most computationally demanding phase of the aforementioned typing methodology (testing phase).
Methods: The testing phase requires the execution of an optimization task on a 1d signal (intensity profile) for a number of type combinations. The introduced algorithm first partitions the signal into individually treatable segments. This parcels the optimization task into a set of more lightweight subproblems, thus reducing the computational effort required for testing a single intensity profile. Then, it eliminates any duplicate optimization subproblems among the type combinations. This way, the computational complexity of the testing phase is significantly restricted.
Results: A dataset of 70 natural samples infected by the human papillomavirus are employed to evaluate the complexity and the accuracy of the proposed algorithm. The obtained results are very promising, indicating that the proposed algorithm is able to octuple or more the speed of virus typing via the PCR-RFLP method, without essentially compromising the accuracy of the employed typing methodology.
Conclusions: The proposed algorithm can be seamlessly integrated into the state-of-the-art typing methodology to significantly increase the throughput of virus typing via the PCR-RFLP method, without harming the methodology’s accuracy. Moreover, it has the potential to be employed in real-time typing applications ? one such application has just been reported.
|
|
|
KEYWORD
|
|
|
PCR-RFLP gel electrophoresis, Virus typing algorithm, Computational complexity restriction, Optimization problem fragmentation
|
|
|
FullTexts / Linksout information
|
|
|
|
|
Listed journal information
|
|
|
|
|